package 双指针法;

import com.alibaba.fastjson.JSON;

import java.util.*;

public class No30串联所有单词的子串 {

    /**
     * 给定一个字符串 s 和一些长度相同的单词 words。
     * 找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
     * 注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。
     *
     * 示例 1：
     * 输入：
     *   s = "barfoothefoobarman",
     *   words = ["foo","bar"]
     * 输出：[0,9]
     * 解释：
     * 从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
     * 输出的顺序不重要, [9,0] 也是有效答案。
     * 示例 2：
     * 输入：
     *   s = "wordgoodgoodgoodbestword",
     *   words = ["word","good","best","word"]
     * 输出：[]
     */

    //参考No567 比较麻烦  但可以AC
    public List<Integer> findSubstring(String s, String[] words) {

        // k:字符串 v:出现的次数
        Map<String,Integer> map=new HashMap<>();
        int[] frep=new int[26];
        boolean[] haveC=new boolean[26];
        int count=0;
        for (String word : words) {
            map.put(word,map.getOrDefault(word,0)+1);
            for (char c : word.toCharArray()) {
                if(frep[c-'a']==0){
                    count++;
                }
                frep[c-'a']++;
                haveC[c-'a']=true;
            }
        }
        List<Integer> list=new ArrayList<>();

        int left=0;
        int right=0;
        int length=words[0].length();
        int allLength=words.length;

        while (right<s.length()){

            char cRight=s.charAt(right);
            right++;

            if(haveC[cRight-'a']){
                frep[cRight-'a']--;
                if(frep[cRight-'a']==0){
                    count--;
                }
            }

            if (right-left>=(length*allLength)){

                if(count==0){
                    list.add(left);
                }

                char cLeft=s.charAt(left);
                left++;

                if(haveC[cLeft-'a']){
                    if(frep[cLeft-'a']==0){
                        count++;
                    }
                    frep[cLeft-'a']++;
                }

            }

        }

        Map<String ,Integer> tempMap=new HashMap<>(map);
        List<Integer> result=new ArrayList<>();
        for (Integer index : list) {
            boolean flag=true;
            for (int i = 0; i < allLength; i++) {

                String str=s.substring(index+length*i,index+length*(i+1));
                Integer integer = map.get(str);
                if(integer!=null&&integer>0){
                    map.put(str,integer-1);
                }else{
                    flag=false;
                    break;
                }

            }
            if(flag) {
                result.add(index);
            }
            map=new HashMap<>(tempMap);
        }

        return result;
    }

    //参考答案   (竟比上面自研的慢了点
    public List<Integer> findSubstringGood(String s, String[] words) {

        Map<String,Integer> map=new HashMap<>();

        for (String word : words) {
            map.put(word,map.getOrDefault(word,0)+1);
        }

        int itemLength=words[0].length();
        int allLength=words.length*itemLength;
        List<Integer> result=new ArrayList<>();
        // i<length-(allLength)

        for (int i = 0; i <= s.length() - allLength; i++) {

            Map<String,Integer> thisMap=new HashMap<>();

            for (int j = 0; j < words.length; j++) {
                int start=i+j*itemLength;
                int end=i+(j+1)*itemLength;
                String str=s.substring(start,end);
                if(!map.containsKey(str)){
                    //没有当前字符串
                    break;
                }
                thisMap.put(str,thisMap.getOrDefault(str,0)+1);
                if(thisMap.get(str)>map.get(str)){
                    break;
                }
                if(j==words.length-1){
                    result.add(i);
                }
            }

        }

        return result;
    }

    public static void main(String[] args) {
        No30串联所有单词的子串 n=new No30串联所有单词的子串();
        String[] arr={"ab","ba"};
        List<Integer> result = n.findSubstringGood("abba", arr);
        System.out.println(JSON.toJSONString(result));
    }

}
